#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1552. 两球之间的磁力
// 【难度】中等
// 【提交】2025.9.25 https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/666033364/
// 【标签】二分查找；贪心算法
const auto _ = std::cin.tie(nullptr)->sync_with_stdio(false);
#define LC_HACK
#ifdef LC_HACK
const auto __ = []() {
    struct ___ {
        static void _() { std::ofstream("display_runtime.txt") << 0 << '\n'; }
    };
    std::atexit(&___::_);
    return 0;
}();
#endif
class Solution {
public:
    bool find(int x,vector<int>& position,int m)
    {
        int count = 1;
        int lastPos = position[0];
        
        for (int i = 1; i < position.size() && count < m; ++i) {
            if (position[i] - lastPos >= x) {
                count++;
                lastPos = position[i];
            }
        }
        return count >= m;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 1, right = position.back() - position[0];
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            find(mid,position,m) ? (ans = mid,left = mid + 1) : right = mid - 1;
        }
        return ans;
    }
};

class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        auto find=[&](int k)
        {
            int pre = position[0],cnt = 1;
            for(int p : position)
            {
                (p - pre >= k) ? (cnt++,pre = p) : 0;
            }
            return cnt >= m;
        };
        ranges::sort(position);
        int n = position.size();
        int left = 1, right = (position.back() - position[0])/(m-1)+2;
        while (left+1 < right) {
            int mid = left + (right - left) / 2;
            (find(mid) ? left : right) = mid;
        }
        return left;
    }
};
/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组position表示篮子的位置，和一个整数m表示需要放置的球的数量。
 * 要求将m个球放入篮子中，使得任意两球之间的最小磁力最大化。
 * 磁力定义为两个球所在篮子位置的距离。
 * 模型：二分查找+贪心验证，通过二分法确定可能的最大最小磁力。
 * 
 * 二、标准解法状态设计
 * 1. 对篮子位置进行排序，便于计算距离。
 * 2. 使用二分查找确定可能的最小磁力，范围是[1, 最大位置-最小位置]。
 * 3. 对于每个候选的最小磁力mid，使用贪心算法验证是否能放置m个球。
 * 4. 贪心策略是从第一个位置开始，尽可能远地放置下一个球。
 * 
 * 三、你的实现思路
 * 使用二分查找法确定可能的最大最小磁力，对于每个候选值使用贪心算法进行验证。
 * 使用标准二分查找模板，在可行时记录答案并尝试更大的值。
 * 
 * 四、逐行注释（带细节提醒）
 * bool find(int x, vector<int>& position, int m) { // 检查函数
 *     int count = 1; // 已放置的球数
 *     int lastPos = position[0]; // 上一个放置球的位置
 *     
 *     for (int i = 1; i < position.size() && count < m; ++i) {
 *         if (position[i] - lastPos >= x) { // 如果距离足够大
 *             count++; // 放置球
 *             lastPos = position[i]; // 更新位置
 *         }
 *     }
 *     return count >= m; // 检查是否成功放置
 * }
 * 
 * int maxDistance(vector<int>& position, int m) {
 *     sort(position.begin(), position.end()); // 排序位置
 *     
 *     int left = 1, right = position.back() - position[0]; // 二分查找边界
 *     int ans = 0; // 记录答案
 *     while (left <= right) { // 标准二分查找模板
 *         int mid = left + (right - left) / 2; // 计算中间值
 *         if (find(mid, position, m)) { // 如果mid可行
 *             ans = mid; // 更新答案
 *             left = mid + 1; // 尝试更大的值
 *         } else {
 *             right = mid - 1; // 尝试更小的值
 *         }
 *     }
 *     return ans; // 返回答案
 * }
 * 
 * 五、正确性证明
 * 二分查找可以正确找到满足条件的最大最小磁力，因为如果某个磁力x可行，那么所有更小的磁力也可行。
 * 贪心策略的正确性基于：为了最大化最小磁力，应该尽可能均匀地放置球，即从第一个位置开始，
 * 每次选择满足最小磁力要求的最远位置。
 * 
 * 六、复杂度
 * 时间：O(n log n + n log D)，其中n是位置数量，D是最大位置差。
 *     排序需要O(n log n)，二分查找需要O(log D)次迭代，每次验证需要O(n)。
 * 空间：O(1)或O(log n)（排序的栈空间）。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法效率高，能够处理较大规模的数据；
 *   - 思路清晰，结合了二分查找和贪心算法的优点；
 *   - 代码实现简洁，易于理解。
 * 缺点：
 *   - 需要先排序，改变了原始数组的顺序；
 *   - 贪心策略的正确性需要一定的理解。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (position.size() < m) return 0;
 * 2. 使用更明确的变量名（如 minForce 代替 x）来增强可读性；
 *   - 对于在线评测，可以移除调试代码；
 * 3. 可以考虑使用更高效的排序算法如果输入范围有限。
 * 
 * 九、一句话总结
 * 通过二分查找确定可能的最大最小磁力，并结合贪心算法进行验证，你的实现高效且准确，
 * 展现了解决最优化问题的能力。
 */